
插入排序（Insertion Sort）是一种简单直观的排序算法，其基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的有序表。具体实现是从第二个元素开始，依次将后面的元素插入到前面已排好序的序列中，直到将整个序列排好序为止。

插入排序的时间复杂度为 $O(n^2)$，虽然不如快速排序、归并排序等高效，但在数据量较小的情况下，插入排序的效率优于其他算法。



```js 
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

```

该算法的思想是将数组分为已排序和未排序两部分，然后逐个将未排序的元素插入到已排序的部分中。具体实现是从第二个元素开始，将其与前面已排序的元素逐个比较，如果前面的元素大于当前元素，则将前面的元素后移一位，直到找到当前元素的插入位置。然后将当前元素插入到该位置，重复以上步骤直到所有元素都被插入到已排序的部分中。插入排序的时间复杂度为 O(n^2)。